In a communication system having a high bit error rate (BER), received data can differ greatly from the transmitted data. The transmitted data is encoded with an error correction code so that errors in the received data can be corrected. The received data must then be decoded in order to reconstruct the transmitted data.
Convolution codes are a type of error correction code, which is widely used in telecommunications. As is known in the art, there are various methods for decoding convolution codes, one of which is the Viterbi decoding algorithm.
A plurality of states is defined for the convolution encoder/decoder. The most common binary convolution codes have 2K−1 states, where the constraint length K is for example, 5, 6, 7 or 9, as in global system for mobile communication (GSM) and code division multiple access (CDMA). Each of the 2K−1 states is an estimation of the K previous bits of the received data.
As is known in the art, Viterbi decoding of binary convolution codes can be represented by a trellis diagram. The trellis diagram is composed of “butterfly” structures, and one such structure is shown in FIG. 1A, to which reference is now made. The trellis diagram illustrates all possible transitions from one state to another. As shown in the butterfly structure, transitions from the old states S2J or S2J+1 can be only to one of the new states SJ and SJ+N/2. This is true for all integral values of a state index J from 0 to N/2−1, where N is the total number of states.
An indication of which transition was made is necessary in order to know whether a new state SJ came from old state S2J or S2J+1. One possible indication would be to store the number of the state, 2J or 2J+1, in memory. Another possible indication, which requires less space in memory, would be to associate a trace bit with each of the possible transitions. In the present example, a “0” trace bit is used when the original state is S2J and a “1” trace bit is used when the original state is S2J+1. An alternative indication could use a “0” trace bit when the original state is S2J and a “1” trace bit when the original state S2J+1.
FIG. 1B, to which reference is now additionally made, shows a portion of the trellis diagram, as is known in the art. In order to simplify the drawing, the trellis diagram is for 16-state binary convolution codes (i.e. a constraint length K of 5). S0 can be reached from either S0 or S1, S8 can be reached from either S0 or S1, S1 can be reached from either S2 or S3 and S9 can be reached from either S2 or S3.
As shown in FIG. 1A, the branches of the trellis diagram are assigned branch metric values, M1 for the transition from S2J to SJ, M2 for the transition from S2J+1 to SJ, M3 for the transition from S2J to SJ+N/2, and M4 for the transition from S2J+1 to SJ+N/2. The branch metric values are dependent upon the symbols in the received data. Techniques for calculating branch metrics are well known in the art and will not be discussed further. H.-L. Lou, “Implementing the Viterbi Algorithm”, IEEE Signal Processing Magazine, September 1995, pp. 42–52, describes a technique for calculating branch metrics.
Moreover, a weight W(SJ) is associated with each state SJ. The weight of a particular new state, also known as its path metric, is calculated according to the following equations:W(new SJ)=max{W(old S2J)+M1, W(old S2J+1)+M2} andW(new SJ+N/2)=max{W(old S2J)+M3, W(old S2J+1)+M4}.
As is well known in the art, an alternative framework for calculating the weight of each state, in which weights and branch metrics are logarithmic values, uses the following equations:W(new SJ)=min{W(old S2J)+M1, W(old S2J+1)+M2} andW(new SJ+N/2)=min{W(old S2J)+M3, W(old S2J+1)+M4}.
The calculation is called an “add-compare-select” (ACS) operation, because the steps are: add the appropriate branch metric value (M1. M2, M3 or M4) to the weight (W(old S2J) and W(old S2J+1)) of the old states from which the new state could have been reached, compare the sums, and select the maximum or minimum sum.
FIG. 1B shows the example of the branch metric values M1, M2, M3 and M4 as 0.25, 0.1, 0.3 and 0.15, respectively, and the initial weights of old S0 and old S1 as 0.3 and 0.4, respectively. The weights of new S0 and new S8 after one step of encoding are 0.55 and 0.7, respectively, according to the following calculations:W(new S0)=max{0.3+0.25, 0.4+0.1}=0.55W(new S8)=max{0.3+0.15, 0.4+0.3}=0.7
According to the Viterbi decoding algorithm, for each source symbol received, there is a transition between states, the set of transitions and states defining a “stage”. The weights of all 2K−1 states in the stage are calculated, and for each of the states, the transition resulting in the maximum weight (or minimum weight, according to the alternative framework mentioned hereinabove) for that state is identified, and the associated trace bit is stored. The trace bit associated with the transition is determined during the “select” step of the “add-compare-select” operation when calculating the weights.
In the single transition of FIG. 1B, the new state S8 has a weight of 0.7. Due to the butterfly structure of the trellis diagram, S8 could have been reached from either S0 or S1. S8 was assigned the maximum weight of 0.7 due to the transition from S1, which is an S2J+1 state, and therefore the trace bit associated with this transition is 1.
When using the Viterbi decoding algorithm, the trace bits are used to trace back the optimal path from a “final” state to an “original” state, the optimal path and the original state enabling reconstruction of the transmitted data. According to one method, one can wait until all of the transmitted symbols have been received in order to begin the trace back. However, due to the limitations of memory space, an alternative method is to begin the decoding procedure when the memory is full, which occurs before all of the transmitted symbols have been received. In the first case, the transmitted symbols generally have a tail of known symbols attached to the end, typically “0” symbols, and therefore S0 is always chosen as the final state from which the trace back decoding is performed. In the second case, the state from which the trace back decoding is performed is the state having the maximum weight (or minimum weight, according to the alternative framework mentioned hereinabove).
In this specification and claims, the term “final state” is used to mean the state from which the trace back decoding begins, whether it is due to a tail or due to memory being full.
Reference is now made to FIG. 2, which is a schematic illustration of an arrangement of trace bits for 1.6-state binary convolution codes in a single 16-bit register 200, as is known in the art. Register 200 can store a trace bit for each of 16 states. Since the weights for states SJ and SJ+8 are calculated from the same butterfly, the order in which the trace bits are determined is S0 and S8, S1 and S9, S2 and S10, etc. The digital signal processor (DSP) TMS320C54x from Texas Instruments Incorporated of Dallas, Tex. USA arranges the trace bits for SJ and SJ+8 next to each other as shown in register 200. This is described in TMS320C54x User's Guide 1995, pp. 3–16, 3–17, and 12–47 to 12–50. The DSP TMS320C54x retains this interleaved arrangement of trace bits when moving the trace bits from the register 200 to a memory cell (not shown).
Reference is now made to FIG. 3, which is an example of a trellis diagram for 16-state binary convolution codes, as is known in the art. For simplicity, the trellis diagram has only 6 stages, involving 6 transitions between states. Reference is made additionally to FIG. 4, which is a schematic illustration of exemplary trace bits for the transitions shown in the trellis diagram of FIG. 3, the trace bits arranged in memory unit 400 according to the arrangement described in FIG. 2. As clarified in the description that follows, the rows of memory unit 400 are filled with trace bits. However, in order to simplify FIG. 4, only those trace bits that are essential to the trace back procedure are shown.
In FIG. 3, each of the 2K−1 initial states has an initial weight. When the first symbol is received, the weights of all possible states in stage 301 are calculated. Based upon the selections made during the ACS operations of the weight calculations, a trace bit for each state of stage 301 is stored in row 401 of memory unit 400. When the next symbol is received, the weights of all possible states in stage 302 are calculated, and a trace bit for each state of stage 302 is stored in row 402 of memory unit 400. This process continues until the final symbol is received or the memory is full. In order to determine the optimal path in the full-memory case, the state of stage 306 having the maximum weight (or minimum weight, according to the alternative framework mentioned hereinabove) is identified, and in the present example, it is S1.
Trace back decoding based on the trace bits is performed from S1 of stage 306. S1 of stage 306 was reached from either S2 of stage 305 or S3 of stage 305. The trace bit stored for S1 in row 406 is 0, so S1 was reached from S2. The trace bit stored for S2 in row 405 is 0, so S2 was reached from S4 of stage 304. The heavy solid lines indicate the complete trace back of states, and the original state is S14. From knowledge of the original state and the collected trace bits of the optimal path, the transmitted data can be reconstructed.
The way in which the trace bits are stored for each of the states and the associated trace back instruction affects the speed of the trace back decoding. The interleaved arrangement of trace bits shown in FIG. 2 makes the trace back decoding rather complex. The DSP TMS320C54x achieves a cycle rate of 6 cycles of trace back for the specific case of a 16-bit register and 16-state binary convolution codes.